#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=300000;
const long long inf=0x7fffffffffffff;

long long min(long long a, long long b) {
  return a<b ? a : b;
}

class Tree {
public:
  int n, m, ind[maxn+1], c[maxn+1], to[2*maxn-1], link[2*maxn-1], val[2*maxn-1];
  long long f[maxn+1][2][3];

  void init(int n) {
    this->n = n;
    m=0;
    for (int i=1; i<=n; i++) {
      ind[i]=0;
    }
  }

  void addSide(int a, int b, int v) {
    m++;
    to[m] = b;
    val[m] = v;
    link[m] = ind[a];
    ind[a] = m;
  }

  void solve(int o, int fa) {
    f[o][1][0]=f[o][1][1]=f[o][0][0]=f[o][0][1]=f[o][0][2]=f[o][1][2]=inf;
    if (c[o]==0) {
      f[o][1][0]=f[o][1][1]=0;
    } else if (c[o]==1) {
      f[o][0][1]=f[o][0][2]=f[o][1][1]=0;
    } else {
      f[o][1][0]=f[o][1][1]=f[o][0][0]=f[o][0][1]=f[o][0][2]=0;
    }
    long long temp[2][3];
    for (int i=ind[o]; i; i=link[i]) {
      if (to[i]!=fa) {
	for(int j=0; j<2; j++) {
	  for (int k=0; k<3; k++) {
	    temp[j][k]=f[o][j][k];
	  }
	}
	f[o][0][0] = temp[0][0]+f[to[i]][0][0];
	f[o][0][1] = min(temp[0][1]+f[to[i]][0][0], temp[0][0]+f[to[i]][0][1]);
	f[o][0][2] = temp[0][2]+f[to[i]][0][2];
	f[o][1][0] = temp[1][0]+f[to[i]][1][0];
	f[o][1][1] = min(temp[1][1]+f[to[i]][1][0], temp[1][0]+f[to[i]][1][1]);
	for (int j=0; j<2; j++) {
	  for (int k=0; k<3; k++) {
	    f[o][0][0] = min(f[o][0][0], temp[0][0]+f[to[i]][j][k]+val[i]);
	    f[o][0][1] = min(f[o][0][1], temp[0][1]+f[to[i]][j][k]+val[i]);
	    f[o][0][2] = min(f[o][0][2], temp[0][2]+f[to[i]][j][k]+val[i]);
	    f[o][1][0] = min(f[o][1][0], temp[1][0]+f[to[i]][j][k]+val[i]);
	    f[o][1][1] = min(f[o][1][1], temp[1][1]+f[to[i]][j][k]+val[i]);
	  }
	}
	for (int j=0; j<2; j++) {
	  for (int k=0; k<3; k++) {
	    if (f[o][j][k]>=inf) {
	      f[o][j][k]=inf;
	    }
	  }
	}
      }
    }
  }

  long long bfs() {
    static int que[maxn+1], fa[maxn+1];
    que[1]=1;
    int h, t;
    for (h=0, t=1; h<t; ) {
      h++;
      for (int i=ind[que[h]]; i; i=link[i]) {
	if (to[i]!=fa[que[h]]) {
	  fa[to[i]]=que[h];
	  que[++t]=to[i];
	}
      }
    } 
    for (int i=t; i>0; i--) {
      solve(que[i], fa[que[i]]);
    }
    return min(f[1][0][0], min(min(f[1][0][1], f[1][0][2]), min(f[1][1][0], f[1][1][1])));
  }
};

int main() {
#ifdef DEBUG
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif

  static Tree g;
  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    int n;
    scanf("%d", &n);
    g.init(n);
    for (int i=1; i<=n; i++) {
      scanf("%d", &g.c[i]);
    }
    for (int i=1; i<n; i++) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);
      g.addSide(u, v, c);
      g.addSide(v, u, c);
    }

    printf("%lld\n", g.bfs());
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
